﻿/*
  KeePass Password Safe - The Open-Source Password Manager
  Copyright (C) 2003-2010 Dominik Reichl <dominik.reichl@t-online.de>

  This program is free software; you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published by
  the Free Software Foundation; either version 2 of the License, or
  (at your option) any later version.

  This program is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  GNU General Public License for more details.

  You should have received a copy of the GNU General Public License
  along with this program; if not, write to the Free Software
  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
*/

using System;
using System.Collections.Generic;
using System.Text;
using System.IO;
using System.Security.Cryptography;
using System.Globalization;
using System.Diagnostics;

using KeePassLib.Utility;

namespace KeePassLib.Cryptography
{
	/// <summary>
	/// Bloom filter-based popular password checking.
	/// </summary>
	public static class PopularPasswords
	{
		private const int PpcTableSize = 4096 * 8; // Bits, multiple of 64

		// Bits set: 15719 of 32768
		// Hash functions: 16
		// Phi (bits unset ratio) estimation: 0.520486428116307
		// Exact Phi: 0.520294189453125
		// False positives ratio: 7.86320618801785E-06
		private static readonly ulong[] PpcTable = {
			0xE4489A3404344788UL, 0x86B25DB476F58AB7UL, 0xB581FAA53EA2342AUL,
			0x70B2C54E1E6762D0UL, 0x1AEEB1A9DF75C01BUL, 0xEE2B0C368A1FE6DAUL,
			0x02DC8D0E5CD9FC17UL, 0x6A449E23057C6560UL, 0x889E159F16E9681DUL,
			0x2686144C0927486FUL, 0x6C4AF58039D4E4D0UL, 0xC5AB193CD0077707UL,
			0x32399D528F7E1F07UL, 0xD6396059B4C04626UL, 0x0E0AF217323143B5UL,
			0x5BD81DA44A6EC64BUL, 0xC2B7AF8E93C4D482UL, 0x92E221F8F7D6F708UL,
			0x91E9933F20E90825UL, 0x5D0AD3B4F81061E3UL, 0x06101FFA010464E7UL,
			0xB10F259524E1BEAAUL, 0x81191B0D13812121UL, 0x2CBEF0BAE5896DA0UL,
			0x4187F900F4B164F8UL, 0x6362BB64B8507748UL, 0x3A622549FE71D89DUL,
			0x052819709952C6CFUL, 0x58EBFBDEACA4D82EUL, 0x2AA0001D0A33CCA0UL,
			0x19EF6C2C114DDC21UL, 0x937F5B504AE709F0UL, 0xD0CD4487EA84F479UL,
			0x169CA49DB21A1338UL, 0x307EF1001D232212UL, 0xB1A42ECB6F61051EUL,
			0x98E28AD44EA4D8F0UL, 0x65820520E5FC0830UL, 0xC231BE1D6054AAD5UL,
			0x3E61CEADDA6AD3A9UL, 0xCE1AA54066469E83UL, 0x3DE3666FB5653C57UL,
			0x39D894D5C6310CA5UL, 0x39CB8A2D5A49CB02UL, 0xDEC88143040007E7UL,
			0x371BFD3E22C20F6DUL, 0x93E1697B64CD8C89UL, 0x67CB5B14CC3ED9EDUL,
			0x6D10DA90332239D6UL, 0x6673DD254CD82162UL, 0x24089D15A893BB0FUL,
			0xEA4D11D96C16A203UL, 0xF70176A0E28539A8UL, 0x0DE6B18BA8966C86UL,
			0x856FC8659A6E9D7FUL, 0x7B726A5A2A6DE203UL, 0x0CFBC2911CB2CE63UL,
			0x6363D417490A0256UL, 0x541A26883DF51A45UL, 0xB37BE5AF83DA3AD1UL,
			0xE7B834E9000CA060UL, 0x841B2F8473222666UL, 0xE16CCFE7029B7E5EUL,
			0x3C08D6AABC226AC9UL, 0x0887968C7690498FUL, 0x3B12659FAC807598UL,
			0xD886F0364EC34407UL, 0x1B31A94B51E024F5UL, 0xC492A4F451800A11UL,
			0x6D89165B69494B89UL, 0x5B183AFD7A22D9B5UL, 0xCDFF381022100872UL,
			0xD29D38A72690562BUL, 0xEFBEE452E0B08682UL, 0x79D755AD7BC57506UL,
			0x38C5372ED560B720UL, 0xB42B16AA623D0378UL, 0x5166ECA60CC145F7UL,
			0x415C4A83F53FA99EUL, 0x3CA25AC6937A92F2UL, 0xDDEE63E44F2B5C9CUL,
			0x580EE47F5FC58ABAUL, 0x7AA9763C6E7BBBD5UL, 0x80420F1F81FBF086UL,
			0xC882A993C8A6AAA0UL, 0x2AE686154F8B3C1AUL, 0x30FE1DA4CA7C74EDUL,
			0x6062AD6F3A825452UL, 0xC53E126449486920UL, 0x9C02CADB149D340CUL,
			0x640F66F165EB961DUL, 0xAC20B871E28D20D6UL, 0x208E878696510DE9UL,
			0x0E9526E74040EE6CUL, 0x39AF5257605AF29EUL, 0x9E0B4A4F372E14ACUL,
			0x74143CD2D734F14DUL, 0x426496359E685811UL, 0x7B63BF2DB9B343C6UL,
			0xB3B40017B49BC96BUL, 0x4BE5B132E6AD8F35UL, 0x0CBDF68541C060F2UL,
			0x5D822A6CF8548376UL, 0xADC77581F25106E4UL, 0x4E91EC63FE2E5847UL,
			0x95167F55FC249D81UL, 0xD4D8F7E04A9F1845UL, 0xD4B55F3F350F10DEUL,
			0x310E105A026E91F8UL, 0xA1DF7398366C1398UL, 0x19D187ADC6C2C26DUL,
			0x1A20235761A2ED08UL, 0xA0B65B813345E3FCUL, 0x208EDBEA6828239FUL,
			0x6745B0810E0DC190UL, 0xDB09F52112896186UL, 0xAAFD7E27B0760AC0UL,
			0x7081DDCC1AEF30F3UL, 0x12744B39E6A8A1E8UL, 0x59A0166D773C5BE4UL,
			0x25426A44E348A784UL, 0x2F117FAF2464B3EFUL, 0x07DE883BA546C9F0UL,
			0x81260E8469A42391UL, 0x7528100996040644UL, 0xB20E1E42F1601FAEUL,
			0x68C9A1A96C5D7002UL, 0x3AE9934E86D51BADUL, 0xCF095403DAC63ED5UL,
			0xAB6F755ECB8064C8UL, 0x8480C7D61D55829FUL, 0x1E7A383A70CBFA6FUL,
			0x2ED63359316544BAUL, 0x4ACCC761760FC489UL, 0x9B668054F469AE2DUL,
			0xCA231AB3FE49327BUL, 0x9164054162F1567BUL, 0x0E276E3BC1FA10AEUL,
			0xB47E34300405D7EFUL, 0xA50FD0B6BF67C75FUL, 0x62BCA28A13A5C2B9UL,
			0x9884F6008C2AE25BUL, 0x80F0D9722D30215CUL, 0xF702F1093AA6AD69UL,
			0x11ECD08A62B902ACUL, 0x32EADD0519A8F117UL, 0x784E07D4E2026220UL,
			0x3803CAC2CDDC9FCDUL, 0x9F55A4559CF9FBCAUL, 0xB64A7C5991550497UL,
			0x632DEF7CE48765A1UL, 0xB7EEC58454987009UL, 0xB798651B5C588074UL,
			0xCF177657608C684FUL, 0x09B886763311529FUL, 0x13279B25F38E9078UL,
			0x4494804869BB8200UL, 0xF3316EF9A5693494UL, 0x6E0DA3E544E21ED9UL,
			0x087F84F0538BD741UL, 0xBC877CCA688983C5UL, 0xF733E7057A2661B4UL,
			0xB503AD77C9E83B23UL, 0x8FB6B2560FCAE443UL, 0xC10E770A2389C1F4UL,
			0x4BBEE81101789902UL, 0xCF28D640F2C4EE03UL, 0xB5FA56647A0D246EUL,
			0xE0E13635CC3A003CUL, 0xAF321B876375B0E0UL, 0x5CC1F60F2CEC1947UL,
			0x6D79F85C6C3E2178UL, 0x8C5105F188F59F48UL, 0xF026E4771132D495UL,
			0x68806C37457C8A11UL, 0xAC4FCFE08FF935E9UL, 0x02C9ED0DE36DEAD0UL,
			0x736E789114C176C0UL, 0x018484BB3F90C627UL, 0xADE11EBC06679C81UL,
			0xDC12310CF4646120UL, 0x565939720A871E91UL, 0x5129FA305D5F80D8UL,
			0x2F1978C44B222F66UL, 0xB2019E9C3C9223A3UL, 0xC26E8310561ABA8BUL,
			0x4C3268947F138A08UL, 0x1B10F12838C2F672UL, 0x3DD765F24A8EAD63UL,
			0xAC255685D091756CUL, 0x1EE8F33DAB66696EUL, 0xDCC69A9317A640E4UL,
			0xB3E10F8B1451577BUL, 0x9C989C1D83694926UL, 0x76C223945AE55AC5UL,
			0x3A5B5A5BA089C4F4UL, 0x5FF9863504F6D63AUL, 0x2BA33660EBC2D7B2UL,
			0xA90E90345E800C21UL, 0xE5C1C600199418DFUL, 0xB05541ED4A60E891UL,
			0xA79B38C035129539UL, 0x101AE63623F00D19UL, 0x86AEF221B04AE1E6UL,
			0x2D5FB8BDF5DD4537UL, 0xCF57F9D3F420CD52UL, 0x41FAB56E1CBEDE7DUL,
			0x4E31A70953DE2053UL, 0xB697E044F555FB02UL, 0x9E32B905F6B54765UL,
			0x0EE565A5E3C49262UL, 0x0E2BEB43000C0363UL, 0xBABF2096A749073FUL,
			0xDE0C27F78E1B89D9UL, 0x14878D174A34D220UL, 0x49189778D3782CF7UL,
			0xC4E37E8E0AFBE8FFUL, 0x0553DB16D17599F3UL, 0xE5324CCC7E3DFAF6UL,
			0x1002D714B914D3E3UL, 0x2C8C0DF862CF9D90UL, 0x552817B44DFF5733UL,
			0xD343B93EE79DA789UL, 0x5B70BB23756C998AUL, 0xB4E79BF903F1B28EUL,
			0xFEC69776A1728BC1UL, 0x3B3481B27815701CUL, 0x8028717CB8AB7835UL,
			0x15C681958C8DAE00UL, 0x44D5CEAEF0A1563CUL, 0x6BB90C05209F1A8EUL,
			0x1323A9FA431DC10DUL, 0x50C7BFFE3DB35371UL, 0x613D8488D33B6D4FUL,
			0x6C300351CF14A712UL, 0xD451A406E06F92D2UL, 0x9D48DC26ABA018B3UL,
			0x1F4573A97CA5FDBAUL, 0x6E65AE090F50F2FBUL, 0x1EBA1E084584BFB3UL,
			0x58BC501FBF7AC020UL, 0x0CF6120722B5D600UL, 0x4ABC91E6DC5000EEUL,
			0x9CBD9C3911614606UL, 0x0BDC8E1A1650977FUL, 0x90383FB6559BCB49UL,
			0x42B98DA163D4411DUL, 0x1C4582B0DBE9F911UL, 0x372C888720E79B05UL,
			0x906560A343786D02UL, 0x9E233DF7175BD4FEUL, 0x4EB66BA91A9C41BFUL,
			0x41FDB3460AC6F231UL, 0x79DB680FA3BA9330UL, 0x5A541224CD43333DUL,
			0x9F3E5B722C0AEEE1UL, 0xA91711FDED89836EUL, 0x80E21258E3E49714UL,
			0x7819026EF352AD7FUL, 0xC293097A18EBEB58UL, 0xCDD60C0948E07C98UL,
			0x444C2170AC4C972AUL, 0xB714CA937966E535UL, 0x6F11F3358AFA71BCUL,
			0xA84E8A3E6892C978UL, 0xE6308B5D0DB90822UL, 0x46E0A95E998B2B86UL,
			0x6A5C6F56AEA55DDBUL, 0x1DB0599111046F3EUL, 0x55D6DB893B553280UL,
			0x62C8F9D71B387563UL, 0x3389047820C4085CUL, 0xA744C6E6B040304BUL,
			0xFD5D213F3F48497DUL, 0xCC5B2117B6532683UL, 0xDC1C19721683F83DUL,
			0x1CB8405C21EB9AADUL, 0x8DB81937DF5C01B6UL, 0x99C6DF745BB3FAEBUL,
			0x450BEAA37F336CEDUL, 0xF0154CEB08FB4623UL, 0xA00293117E29034BUL,
			0xA66DD9AC091740E8UL, 0xB4E7455E47738348UL, 0x9BF6AB384A17588BUL,
			0x355EA7E660615307UL, 0x29973430E7BD32C1UL, 0xFCF99196BA1453FEUL,
			0x561E4A9749A31000UL, 0x996E40ACB907907CUL, 0x8C068A537891D817UL,
			0xDB42112F997B7851UL, 0xFA785497B0DBA777UL, 0x28AEF904C18EE0E3UL,
			0x8A70C563CE4B4567UL, 0x56A968C07D246D99UL, 0xFD327FAD0450EF8DUL,
			0x00C7DA2B6C9F79F5UL, 0xCF6280916EBF0129UL, 0xAC978A54BDD2071DUL,
			0x2D41D3E0C76E3F32UL, 0x63425615DB3281B4UL, 0x481BB08F50D69823UL,
			0x5F80EE74AC0BE2BDUL, 0x0D3AC9CC76A2D632UL, 0xEDB7C0E219D80DFAUL,
			0xCD2FA275D82EB2B6UL, 0x41898B02F28A159DUL, 0x1BD46018489C80B8UL,
			0x3AE0AECD4BB1127DUL, 0xA0FF48E7432058DFUL, 0xD1CC9C721482F42CUL,
			0x7B0FB481B5F19E03UL, 0xA221FDB32FC9174BUL, 0x1FE31F128748AD5CUL,
			0xA9C80E0BB849C784UL, 0x9725ED5C207DEAB2UL, 0x8EEC7C5310933D31UL,
			0xDE590C192A0B27B4UL, 0xE51CE519B6437021UL, 0x6E1057997FB1DEAEUL,
			0xC57DF8FEB45EE6A4UL, 0xDE24D5C87D4555E2UL, 0xF00FC5511FE008C1UL,
			0xC664EFBB36A481EDUL, 0x58688CC427EC4CC7UL, 0x254829013B0E76AEUL,
			0xECD1857ED61869A5UL, 0x64CE789BDE508F7DUL, 0xF295CAAA594ECC58UL,
			0x8F5B58B79C94EBE0UL, 0xA39BF312E6C61A6CUL, 0x0D00969829C5502BUL,
			0xB8C13C1FC5CB718DUL, 0x3224118DA915B5EFUL, 0x10EC24C2121DD4D7UL,
			0x1FB788E5D8E03357UL, 0x5E9F86D0099CE632UL, 0x673ED65F677821B0UL,
			0x312A41E1B51549F9UL, 0x00DF25E45DAD76E2UL, 0x5A1561911C876B19UL,
			0x1A58EF968CC11787UL, 0x029599EB8BD8719AUL, 0xEA27B36FFF5930F7UL,
			0x04060010169D7A62UL, 0x5630B4458FBA3A71UL, 0xB9CB8F84D66A93F8UL,
			0x3428A1C10490B5BAUL, 0x7E5857F34A1482F7UL, 0xCC62980D2ADAC41DUL,
			0x903EC89CC55BD0CEUL, 0xFE9EC99089004024UL, 0xECD3E226F9BE420CUL,
			0x17475B3D71CCA656UL, 0x5CCBD2176CA8DE01UL, 0xB13675D62856894CUL,
			0x744032E639C3F11FUL, 0x0E349612CEAF382AUL, 0x41E516CDA67BB4DCUL,
			0x343CB2990641694AUL, 0xEF1EE7E82B7E65CAUL, 0x32D3BD01D421A7CBUL,
			0xD7FC605717AF512CUL, 0x62D776335ACAA6A6UL, 0xFDA7C7EFBEFFB24DUL,
			0x1DA4421BE204563FUL, 0x7AC5071D7D6439ECUL, 0xB04907D74291F402UL,
			0x1622EAB93909C0BEUL, 0x0104D4A240D85592UL, 0x902DAC0ADEE44311UL,
			0xC1A9DFE403C0DA20UL, 0xF625780DB1B3F871UL, 0x75AB40C313DF9E55UL,
			0xDFAE2CD087187B45UL, 0x417D7807D2171F9FUL, 0xCD1D1A444D86DF78UL,
			0x87DE186A752CDB73UL, 0xEDEBA23523A0DC64UL, 0x10AA6B0C35F6B110UL,
			0x38C31C863D4F4ED5UL, 0x7A4665420070B621UL, 0x4F2B5963CE4F5F6CUL,
			0x1960F7AD866513A3UL, 0x3A7C924A978F8251UL, 0x56B8481940FDF39AUL,
			0x11643EEFEEE1ACA6UL, 0xED127C507EF6C54CUL, 0xB5EBD3BFA89E9F67UL,
			0x21879F26D4BE4A14UL, 0x8D6154A8A2027EA6UL, 0x1C69E882730B93C8UL,
			0x8D7B11D1DD98B5F2UL, 0x76A7FAA7A888B1FBUL, 0x90A971E4C8F7AE28UL,
			0x56A4D02DF123F5EAUL, 0x44A05664A7F03956UL, 0x309C6C63418B2616UL,
			0x108CA042607E272AUL, 0x4AB8F3508ADDA60CUL, 0xA7FBBAF0BB17714BUL,
			0x3CC8A384E2D96A84UL, 0x391E782A19AD5190UL, 0x23065DCE40659703UL,
			0xC530D54413A3791EUL, 0x803E3C294BE1C26EUL, 0x61ABAAC14D74EC54UL,
			0xA4F72A046456894DUL, 0x242893DB0DB83BB0UL, 0xD34E3160ADCB5CAFUL,
			0x70DC7C26C140E652UL, 0xC61E965117931ED2UL, 0x6E292C67D1F4C3A7UL,
			0xCBF4C4668630AD09UL, 0x89E71E5660F60C09UL, 0xB94E78B3D69CF448UL,
			0x34F7E505129E67E8UL, 0x2B5692EB2F9ADB1FUL, 0x18B33EB5C6218B92UL,
			0x69B0107420A2245FUL, 0x882D9A53746BB452UL, 0xD672B7869EA7CFD9UL,
			0x19A7272D0738C53FUL, 0x1322E47C89337EB2UL, 0x812E69C0245E50D7UL,
			0xF187AA4541ABDDD3UL, 0x8FEAA798A615B748UL, 0x667E3C139D8B56C8UL,
			0xAEC9BF9F45CA5D44UL, 0xFBB9142069E57883UL, 0x094C75FB9845661DUL,
			0x23A6C5F02F3A6C55UL, 0x9A16DA92770C6ECCUL, 0xF748C20B24D1DC6FUL,
			0x7ACB623BBD295332UL, 0xEAEF79479E38A94CUL, 0x704D58570E2E5332UL,
			0x036F52F5A9684E7CUL, 0xEC738490914BA27EUL, 0xF9278559E81D901EUL,
			0x49821AAC204B64C2UL, 0x990985242F9C9A31UL, 0x06A3649A1BA11E75UL,
			0xE4A1A9808B319814UL, 0x18A4498A7BBA0060UL, 0x75ED340849D3CCA3UL,
			0x82225D786972A9E0UL, 0x8EADE60B8E678CD5UL, 0xC99BB41C1726AABDUL,
			0x2AB9C9C8FAC6DC30UL, 0x0441780010493500UL, 0xDDDDE54767F517ADUL,
			0x56DB8BCC493B8490UL, 0xD1A6739A09D42053UL, 0x617912F0246C3648UL,
			0x6ADF565B9B17101DUL, 0x0CA0C0BEC98D33BBUL, 0xC920D715A451BC53UL,
			0xA10E436864547E8FUL, 0x8A2686E7564305BAUL, 0xF5454820A996BC1FUL,
			0xC9216226D09DDC39UL, 0x68A0E58CAE5C7DB9UL, 0x7F5252D3EA712008UL,
			0x5BC5B55C5F4A9803UL, 0xAFC544F4F2E4002EUL, 0x6C42C429889A7D5CUL,
			0x2F4F73AA425DEFA6UL, 0x2E6AFD00A266DEF0UL, 0x49CACCAAE1B2C278UL,
			0xB62663F96D79781DUL, 0x87E5E67912BAD6F9UL, 0x93BF4AB146F447CFUL,
			0xC942B3D03448F513UL, 0x50B6C04EC1C35605UL, 0x010B453F9ACBF9DDUL,
			0x84CB000D0AA3E002UL, 0xB0AFA8BD656B2A9AUL, 0x736BC06ADC0DBADFUL,
			0x18C9AE72A4F7F14DUL, 0x8B20226817FED9F7UL, 0x488201718D3F25AAUL,
			0xB436031BF234430AUL, 0x301B579C25A81F6CUL, 0x94AD1143EF48395BUL,
			0xD18DAC91770DE980UL, 0xB8B8E0C504956DE5UL, 0xDDC58A6B8AF36BD0UL,
			0x70288138236C8C2EUL, 0x12566E4A4C2B5769UL, 0x323D3516D4611368UL,
			0xC8A045E9E3E20B1FUL, 0x1B69C6DCD29AAE04UL, 0x24DA7006D030D431UL,
			0x468A8E0A5523AF97UL, 0x075CABD7CAC6346DUL, 0x6AA5CE224365EB50UL,
			0x888443448F8FC9F1UL, 0x4D04602CAD6D5208UL, 0x84FC44D5FE8D928EUL,
			0x703E412307FC7C32UL, 0xAFBAEAA0E3D8BBAAUL, 0x7C32F528AA001332UL,
			0x86BB81913BB879C7UL, 0x99853897C46219ABUL, 0xA213ED45FD500DD2UL,
			0xD591D1A722685833UL, 0x33305B089DCD5298UL, 0x52D2E2138D12701CUL,
			0x99B931133F6A60CDUL, 0x2633C5A928D65828UL
		};

		public static bool IsPopularPassword(char[] vPassword)
		{
			Debug.Assert(PpcTable.Length == (PpcTableSize / 64));

			if(vPassword == null) throw new ArgumentNullException("vPassword");
			if(vPassword.Length == 0) return false;

			foreach(char ch in vPassword)
			{
				if(!IsPopularChar(ch)) return false;
			}

			UTF8Encoding utf8 = new UTF8Encoding(false);
			byte[] pbUtf8 = utf8.GetBytes(vPassword);

			int[] vIndices = GetTableIndices(pbUtf8, PpcTableSize);
			Array.Clear(pbUtf8, 0, pbUtf8.Length);

			foreach(int iIndex in vIndices)
			{
				if(!GetTableBit(PpcTable, iIndex)) return false;
			}

			return true;
		}

		private static bool IsPopularChar(char ch)
		{
			return (((ch >= 'A') && (ch <= 'Z')) || ((ch >= 'a') && (ch <= 'z')) ||
				((ch >= '0') && (ch <= '9')) || (ch == '_') || (ch == '!'));
		}

		private static int[] GetTableIndices(byte[] pbPasswordUtf8, int nTableSize)
		{
			Debug.Assert((nTableSize >= 2) && (nTableSize <= 0x10000));
			Debug.Assert((nTableSize % 64) == 0);

			SHA512Managed sha = new SHA512Managed();
			byte[] pbHash = sha.ComputeHash(pbPasswordUtf8);

			int[] vIndices = new int[pbHash.Length / 4]; // 4 by experiment
			for(int i = 0; i < vIndices.Length; ++i)
				vIndices[i] = ((((int)pbHash[i * 2] << 8) |
					(int)pbHash[i * 2 + 1]) % nTableSize);

			return vIndices;
		}

		private static bool GetTableBit(ulong[] vTable, int iBit)
		{
			return ((vTable[iBit >> 6] & (1UL << (iBit & 0x3F))) != 0UL);
		}

#if (DEBUG && !KeePassLibSD)
		private static bool SetTableBit(ulong[] vTable, int iBit)
		{
			if(GetTableBit(vTable, iBit)) return false;

			vTable[iBit >> 6] = (vTable[iBit >> 6] | (1UL << (iBit & 0x3F)));
			return true;
		}

		public static void MakeList()
		{
			string strData = File.ReadAllText("MostPopularPasswords.txt", Encoding.UTF8);
			strData += " ";
			CharStream cs = new CharStream(strData);

			List<string> vPasswords = new List<string>();
			StringBuilder sbPassword = new StringBuilder();
			while(true)
			{
				char ch = cs.ReadChar();
				if(ch == char.MinValue) break;

				if(char.IsWhiteSpace(ch))
				{
					string strPassword = sbPassword.ToString();
					strPassword = strPassword.ToLower();

					if(strPassword.Length > 3)
					{
						if(vPasswords.IndexOf(strPassword) < 0)
							vPasswords.Add(strPassword);
					}

					sbPassword = new StringBuilder();
				}
				else
				{
					Debug.Assert(!char.IsControl(ch) && !char.IsHighSurrogate(ch) &&
						!char.IsLowSurrogate(ch) && !char.IsSurrogate(ch));
					Debug.Assert(IsPopularChar(ch));
					sbPassword.Append(ch);
				}
			}

			ulong[] vTable = new ulong[PpcTableSize / 64];
			Array.Clear(vTable, 0, vTable.Length);

			long lBitsInTable = 0;
			UTF8Encoding utf8 = new UTF8Encoding(false);
			foreach(string strPassword in vPasswords)
			{
				byte[] pbUtf8 = utf8.GetBytes(strPassword);
				int[] vIndices = GetTableIndices(pbUtf8, PpcTableSize);

				foreach(int i in vIndices)
				{
					if(SetTableBit(vTable, i)) ++lBitsInTable;
				}
			}

			StringBuilder sb = new StringBuilder();
			sb.Append("\t\t\t");
			for(int i = 0; i < vTable.Length; ++i)
			{
				if(i > 0)
				{
					if((i % 3) == 0)
					{
						sb.AppendLine(",");
						sb.Append("\t\t\t");
					}
					else sb.Append(", ");
				}

				sb.Append("0x");
				sb.Append(vTable[i].ToString("X16"));
				sb.Append("UL");
			}

			sb.AppendLine();
			sb.AppendLine();
			sb.AppendLine("Bits set: " + lBitsInTable.ToString() + " of " +
				PpcTableSize.ToString());
			int cHashFn = GetTableIndices(utf8.GetBytes("Dummy"), PpcTableSize).Length;
			sb.AppendLine("Hash functions: " + cHashFn.ToString());
			double dblPhi = Math.Pow(1.0 - ((double)cHashFn / PpcTableSize),
				(double)vPasswords.Count);
			sb.AppendLine("Phi (bits unset ratio) estimation: " +
				dblPhi.ToString(CultureInfo.InvariantCulture));
			dblPhi = ((double)(PpcTableSize - lBitsInTable) / (double)PpcTableSize);
			sb.AppendLine("Exact Phi: " + dblPhi.ToString(CultureInfo.InvariantCulture));
			sb.AppendLine("False positives ratio: " + Math.Pow(1.0 - dblPhi,
				(double)cHashFn).ToString(CultureInfo.InvariantCulture));

			File.WriteAllText("Table.txt", sb.ToString());
		}
#endif
	}
}
